package LeetCode;

public class LC_134_GasStation {
    public static void main(String[] args) {

    }

    static class Solution {
        public int canCompleteCircuit(int[] gas, int[] cost) {
            int length = gas.length;
            if (length != cost.length) return -1;
            int[] minus = new int[length];
            for (int i = 0; i < length; i++) minus[i] = gas[i] - cost[i];
            int start, end;
            for (start = 0; start < length; start++) {
                int remain = 0;
                for (end = start; Math.abs(end - start) <= length - 1; end++) {
                    remain += minus[end % length];
                    while (remain < 0) {
                        remain -= minus[start++];
                        if (start >= length) return -1;
                    }
                }
                if (Math.abs(end - start) > length - 1) break;
            }
            if (start >= length) return -1;
            return start;
        }
    }
}
